C/sorting.and.searching.cormen.algo/Introduction to Algorithms, Third Edition/code/has.c

   1 /* hash table */
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5
   6 /* implementation dependent declarations */
   7 typedef int keyType;            /* type of key */
   8
   9 /* user data stored in hash table */
  10 typedef struct {
  11     int stuff;                  /* optional related data */
  12 } recType;
  13
  14 typedef int hashIndexType;      /* index into hash table */
  15
  16 #define compEQ(a,b) (a == b)
  17
  18
  19 /* implementation independent declarations */
  20 typedef enum {
  21     STATUS_OK,
  22     STATUS_MEM_EXHAUSTED,
  23     STATUS_KEY_NOT_FOUND
  24 } statusEnum;
  25
  26 typedef struct nodeTag {
  27     struct nodeTag *next;       /* next node */
  28     keyType key;                /* key */
  29     recType rec;                /* user data */
  30 } nodeType;
  31
  32 nodeType **hashTable;
  33 int hashTableSize;
  34
  35 hashIndexType hash(keyType key) {
  36
  37    /***********************************
  38     *  hash function applied to data  *
  39     ***********************************/
  40
  41     return (key % hashTableSize);
  42 }
  43
  44 statusEnum insert(keyType key, recType *rec) {
  45     nodeType *p, *p0;
  46     hashIndexType bucket;
  47
  48    /************************************************
  49     *  allocate node for data and insert in table  *
  50     ************************************************/
  51
  52     /* insert node at beginning of list */
  53     bucket = hash(key);
  54     if ((p = malloc(sizeof(nodeType))) == 0)
  55         return STATUS_MEM_EXHAUSTED;
  56     p0 = hashTable[bucket];
  57     hashTable[bucket] = p;
  58     p->next = p0;
  59     p->key = key;
  60     p->rec = *rec;
  61     return STATUS_OK;
  62 }
  63
  64 statusEnum delete(keyType key) {
  65     nodeType *p0, *p;
  66     hashIndexType bucket;
  67
  68    /********************************************
  69     *  delete node containing data from table  *
  70     ********************************************/
  71
  72     /* find node */
  73     p0 = 0;
  74     bucket = hash(key);
  75     p = hashTable[bucket];
  76     while (p && !compEQ(p->key, key)) {
  77         p0 = p;
  78         p = p->next;
  79     }
  80     if (!p) return STATUS_KEY_NOT_FOUND;
  81
  82     /* p designates node to delete, remove it from list */
  83     if (p0)
  84         /* not first node, p0 points to previous node */
  85         p0->next = p->next;
  86     else
  87         /* first node on chain */
  88         hashTable[bucket] = p->next;
  89
  90     free (p);
  91     return STATUS_OK;
  92 }
  93
  94 statusEnum find(keyType key, recType *rec) {
  95     nodeType *p;
  96
  97    /*******************************
  98     *  find node containing data  *
  99     *******************************/
 100
 101     p = hashTable[hash(key)];
 102     while (p && !compEQ(p->key, key))
 103         p = p->next;
 104     if (!p) return STATUS_KEY_NOT_FOUND;
 105     *rec = p->rec;
 106     return STATUS_OK;
 107 }
 108
 109 int main(int argc, char **argv) {
 110     int i, maxnum, random;
 111     recType *rec;
 112     keyType *key;
 113     statusEnum err;
 114
 115     /* command-line:
 116      *
 117      *   has maxnum hashTableSize [random]
 118      *
 119      *   has 2000 100
 120      *       processes 2000 records, tablesize=100, sequential numbers
 121      *   has 4000 200 r
 122      *       processes 4000 records, tablesize=200, random numbers
 123      *
 124      */
 125     maxnum = atoi(argv[1]);
 126     hashTableSize = atoi(argv[2]);
 127     random = argc > 3;
 128
 129     if ((rec = malloc(maxnum * sizeof(recType))) == 0) {
 130         fprintf (stderr, "out of memory (rec)\n");
 131         exit(1);
 132     }
 133     if ((key = malloc(maxnum * sizeof(keyType))) == 0) {
 134         fprintf (stderr, "out of memory (key)\n");
 135         exit(1);
 136     }
 137
 138     if ((hashTable = calloc(hashTableSize, sizeof(nodeType *))) == 0) {
 139         fprintf (stderr, "out of memory (hashTable)\n");
 140         exit(1);
 141     }
 142
 143     if (random) { /* random */
 144         /* fill "key" with unique random numbers */
 145         for (i = 0; i < maxnum; i++) key[i] = rand();
 146         printf ("ran ht, %d items, %d hashTable\n", maxnum, hashTableSize);
 147     } else {
 148         for (i=0; i<maxnum; i++) key[i] = i;
 149         printf ("seq ht, %d items, %d hashTable\n", maxnum, hashTableSize);
 150     }
 151
 152
 153     for (i = 0; i < maxnum; i++) {
 154         err = insert(key[i], &rec[i]);
 155         if (err) printf("pt1, i=%d\n", i);
 156     }
 157
 158     for (i = maxnum-1; i >= 0; i--) {
 159         err = find(key[i], &rec[i]);
 160         if (err) printf("pt2, i=%d\n", i);
 161     }
 162
 163     for (i = maxnum-1; i >= 0; i--) {
 164         err = delete(key[i]);
 165         if (err) printf("pt3, i=%d\n", i);
 166     }
 167     return 0;
 168 }